`
https://leetcode.cn/problems/greatest-sum-divisible-by-three/
`

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumDivThree = function (nums) {
  // 定义：nums[0..i] 中，和 3 相除余数为 j 的最大和是 dp[i][j]
  const dp = Array.from({ length: nums.length + 1 }, () => new Array(3).fill(0))

  // 没有数字时，余数为 0 的最大和为 0，不存在余数为 1 或 2 的情况
  dp[0][0] = 0
  dp[0][1] = -Infinity
  dp[0][2] = -Infinity

  for (let i = 1; i <= nums.length; i++) {
    // 有一位偏差，所以第 i 个数字是 nums[i - 1]
    const curNum = nums[i - 1]
    if (curNum % 3 === 0) {
      // dp[i][0] = Math.max(dp[i - 1][0] + curNum, dp[i - 1][0])
      // dp[i][1] = Math.max(dp[i - 1][1] + curNum, dp[i - 1][1])
      // dp[i][2] = Math.max(dp[i - 1][2] + curNum, dp[i - 1][2])
      // 可化简：
      dp[i][0] = dp[i - 1][0] + curNum
      dp[i][1] = dp[i - 1][1] + curNum
      dp[i][2] = dp[i - 1][2] + curNum
    } else if (curNum % 3 === 1) {
      dp[i][0] = Math.max(dp[i - 1][2] + curNum, dp[i - 1][0]);
      dp[i][1] = Math.max(dp[i - 1][0] + curNum, dp[i - 1][1]);
      dp[i][2] = Math.max(dp[i - 1][1] + curNum, dp[i - 1][2]);
    } else {
      dp[i][0] = Math.max(dp[i - 1][1] + curNum, dp[i - 1][0]);
      dp[i][1] = Math.max(dp[i - 1][2] + curNum, dp[i - 1][1]);
      dp[i][2] = Math.max(dp[i - 1][0] + curNum, dp[i - 1][2]);
    }
  }

  return dp[nums.length][0]
};